{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Compute the Number of Combinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A function to calculate the number of combinations for creating subsequences of *k* elements out of a sequence with *n* elements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> from mlxtend.math import num_combinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Combinations are selections of items from a collection regardless of the order in which they appear (in contrast to permutations). For example, let's consider a combination of 3 elements (k=3) from a collection of 5 elements (n=5): \n",
    "\n",
    "- collection: {1, 2, 3, 4, 5}\n",
    "- combination 1a: {1, 3, 5} \n",
    "- combination 1b: {1, 5, 3}\n",
    "- combination 1c: {3, 5, 1}\n",
    "- ...\n",
    "- combination 2: {1, 3, 4}\n",
    "\n",
    "In the example above the combinations 1a, 1b, and 1c, are the \"same combination\" and counted as \"1 possible way to combine items 1, 3, and 5\" -- in combinations, the order does not matter.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The number of ways to combine elements (**without replacement**)  from a collection with size *n* into subsets of size *k* is computed via the binomial coefficient (\"*n* choose *k*\"):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{pmatrix} \n",
    "n  \\\\\n",
    "k \n",
    "\\end{pmatrix} = \\frac{n(n-1)\\ldots(n-k+1)}{k(k-1)\\dots1} = \\frac{n!}{k!(n-k)!}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To compute the number of combinations **with replacement**, the following, alternative equation \n",
    "is used (\"*n* multichoose *k*\"):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\begin{pmatrix} \n",
    "n  \\\\\n",
    "k \n",
    "\\end{pmatrix} = \\begin{pmatrix} \n",
    "n + k -1  \\\\\n",
    "k \n",
    "\\end{pmatrix}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### References\n",
    "\n",
    "- [https://en.wikipedia.org/wiki/Combination](https://en.wikipedia.org/wiki/Combination)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 1 - Compute the number of combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of ways to combine 20 elements into 8 subelements: 125970\n"
     ]
    }
   ],
   "source": [
    "from mlxtend.math import num_combinations\n",
    "\n",
    "c = num_combinations(n=20, k=8, with_replacement=False)\n",
    "print('Number of ways to combine 20 elements'\n",
    "      ' into 8 subelements: %d' % c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of ways to combine 20 elements into 8 subelements (with replacement): 2220075\n"
     ]
    }
   ],
   "source": [
    "from mlxtend.math import num_combinations\n",
    "\n",
    "c = num_combinations(n=20, k=8, with_replacement=True)\n",
    "print('Number of ways to combine 20 elements'\n",
    "      ' into 8 subelements (with replacement): %d' % c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 2 - A progress tracking use-case"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is often quite useful to track the progress of a computational expensive tasks to estimate its runtime. Here, the `num_combination` function can be used to compute the maximum number of loops of a `combinations` iterable from itertools:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Progress: 56/56"
     ]
    }
   ],
   "source": [
    "import itertools\n",
    "import sys\n",
    "import time\n",
    "from mlxtend.math import num_combinations\n",
    "\n",
    "items = {1, 2, 3, 4, 5, 6, 7, 8}\n",
    "max_iter = num_combinations(n=len(items), k=3, \n",
    "                            with_replacement=False)\n",
    "\n",
    "for idx, i in enumerate(itertools.combinations(items, r=3)):\n",
    "    # do some computation with itemset i\n",
    "    time.sleep(0.1)\n",
    "    sys.stdout.write('\\rProgress: %d/%d' % (idx + 1, max_iter))\n",
    "    sys.stdout.flush()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## API"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "## num_combinations\n",
      "\n",
      "*num_combinations(n, k, with_replacement=False)*\n",
      "\n",
      "Function to calculate the number of possible combinations.\n",
      "\n",
      "**Parameters**\n",
      "\n",
      "- `n` : `int`\n",
      "\n",
      "    Total number of items.\n",
      "\n",
      "- `k` : `int`\n",
      "\n",
      "    Number of elements of the target itemset.\n",
      "\n",
      "- `with_replacement` : `bool` (default: False)\n",
      "\n",
      "    Allows repeated elements if True.\n",
      "\n",
      "**Returns**\n",
      "\n",
      "- `comb` : `int`\n",
      "\n",
      "    Number of possible combinations.\n",
      "\n",
      "**Examples**\n",
      "\n",
      "For usage examples, please see\n",
      "    [http://rasbt.github.io/mlxtend/user_guide/math/num_combinations/](http://rasbt.github.io/mlxtend/user_guide/math/num_combinations/)\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "with open('../../api_modules/mlxtend.math/num_combinations.md', 'r') as f:\n",
    "    print(f.read())"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
